package com.sheng.leetcode.year2023.month04.day19;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/04/19
 * <p>
 * 1043. 分隔数组以得到最大和<p>
 * <p>
 * 给你一个整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。<p>
 * 分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。<p>
 * 返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。<p>
 * <p>
 * 示例 1：<p>
 * 输入：arr = [1,15,7,9,2,5,10], k = 3<p>
 * 输出：84<p>
 * 解释：数组变为 [15,15,15,9,10,10,10]<p>
 * <p>
 * 示例 2：<p>
 * 输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4<p>
 * 输出：83<p>
 * <p>
 * 示例 3：<p>
 * 输入：arr = [1], k = 1<p>
 * 输出：1<p>
 * <p>
 * 提示：<p>
 * 1 <= arr.length <= 500<p>
 * 0 <= arr[i] <= 10^9<p>
 * 1 <= k <= arr.length<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/partition-array-for-maximum-sum">1043. 分隔数组以得到最大和</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1043 {

    @Test
    public void test01() {
        int[] arr = {1, 15, 7, 9, 2, 5, 10};
        int k = 3;
//        int[] arr = {1, 4, 1, 5, 7, 3, 6, 1, 9, 9, 3};
//        int k = 4;
//        int[] arr = {1};
//        int k = 1;
        System.out.println(new Solution().maxSumAfterPartitioning(arr, k));
    }
}

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        // 将数组 arr 分割为最长为 k 的连续子数组，并且子数组内的所有元素都是其子数组内的最大值，求总和最大值
        // 思路：动态规划
        int length = arr.length;
        // max[i] 代表数组中前 i 个元素分割后的和
        int[] max = new int[length + 1];
        for (int i = 1; i <= length; i++) {
            // 表示最后一个子数组中的最大值
            int mx = 0;
            // 从右往左枚举最后一个子数组的第一个元素 arr[j - 1]
            for (int j = i; j > Math.max(0, i - k); j--) {
                mx = Math.max(mx, arr[j - 1]);
                max[i] = Math.max(max[i], max[j - 1] + mx * (i - j + 1));
            }
        }
        return max[length];
    }
}
